//bases on Mark Nelson implementation of GST

package ru.osu.acm.system.sourcediff;

import java.util.*;

public class GST {

        private String tekst[];


    private String G;
    private ST ST;

    public GST(String text1, String text2, char T1, char T2) {
        this(new String[]{text1, text2}, new char[]{T1, T2});
    }


    private int getGSubLength(int n) {
        int length = 0;
        for (int i = 0; i <= n; i++) {
            length += tekst[i].length() + 1;
        }
        return length - 1;
    }


    public class comSubstr {
        private int beginIndes[];
        private int endIndes[];

        public comSubstr(int beginIndes[], int endIndes[]) {
            this.beginIndes = beginIndes;
            this.endIndes = endIndes;
        }

        public comSubstr(int beginIndes[], int max) {
            this.beginIndes = beginIndes;
            endIndes = new int[tekst.length];
            for(int i=0; i<tekst.length; i++) {
                endIndes[i] = beginIndes[i] + max - 1;
            }
        }

        public int[] getBeginIndes() {
            return beginIndes;
        }

        public int[] getEndIndes() {
            return endIndes;
        }
    }

    public comSubstr getLcs() {
        int beginIndes[] = new int[tekst.length];
        int endIndes[] = new int[tekst.length];
        initBeginEndIndes(beginIndes, endIndes);
        return getLcs(beginIndes, endIndes);
    }

    private void initBeginEndIndes(int beginIndes[], int endIndes[]) {
        beginIndes[0] = 0;
        endIndes[0] = tekst[0].length();

        for(int i=1; i<tekst.length; i++) {
            beginIndes[i] = endIndes[i-1]+1;
            endIndes[i] = beginIndes[i]+tekst[i].length();
        }
    }

    public GST(String tekst[], char Ts[]) {
        this.tekst = tekst;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tekst.length; i++) {
            sb.append(tekst[i]);
            sb.append(Ts[i]);
        }
        G = sb.toString();
        ST = new ST(G);
        fiksLenSufes(ST.getRootUzel());
    }

      public int[] getDefBeginIndes() {
        int beginIndes[] = new int[tekst.length];
        initBeginEndIndes(beginIndes, new int[tekst.length]);
        return beginIndes;
    }

    public int[] getDefEndIndes() {
        int endIndes[] = new int[tekst.length];
        initBeginEndIndes(new int[tekst.length], endIndes);
        return endIndes;
    }



    public int[] incIndes(int Indes[]) {
        for(int i=0; i<tekst.length; i++)
            Indes[i]++;
        return Indes;
    }

    private void fiksLenSufes(Uzel Uzel) {
        for (Rebro Rebro : Uzel.getRebros()) {
            for (int i = 0; i < tekst.length; i++) {
                if ((Rebro.getBeginInd() <= getGSubLength(i)) &&
                        (Rebro.getEndInd() > getGSubLength(i))) {

                    Rebro.setEndInd(getGSubLength(i));
                }
            }
            fiksLenSufes(Rebro.getEndUzel());
        }
    }





    public comSubstr getLcs(int beginIndes[], int endIndes[]) {
        Map<Uzel, LCSUzelStatus> statuses = new HashMap<Uzel, LCSUzelStatus>();
        getLCSUzelStatus(ST.getRootUzel(), 0, statuses);

        comSubstr comSubstr = getLcs(beginIndes, endIndes, statuses);
        statuses.clear();

        return comSubstr;
    }

    private comSubstr getLcs(int beginIndes[], int endIndes[], Map<Uzel, LCSUzelStatus> statuses) {
        int max = 0;
        int foundBeginIndes[] = null;

        for (LCSUzelStatus status : statuses.values()) {
            if ((status.getDlina() > 0) && (status.isAllStrings()) && (max <= status.getDlina())) {
                Uzel Uzel = status.getUzel();
                int workingBeginIndes[] = initFoundBeginIndes();

                updFoundBeginIndes(beginIndes, endIndes, Uzel, status.getDlina(),
                        statuses, workingBeginIndes);

                if (verifyFoundBeginIndes(workingBeginIndes)) {
                    foundBeginIndes = workingBeginIndes;
                    max = status.getDlina();
                }
            }
        }

        if (foundBeginIndes == null)
            return null;

        return new comSubstr(foundBeginIndes, max);
    }

    private int[] initFoundBeginIndes() {
        int beginIndes[] = new int[tekst.length];
        for(int i=0; i<tekst.length; i++)
            beginIndes[i] = Integer.MAX_VALUE;
        return beginIndes;
    }

    private void updFoundBeginIndes(int beginIndes[], int endIndes[], Uzel Uzel, int Dlina,
                                            Map<Uzel, LCSUzelStatus> statuses, int[] foundBeginIndes) {
        for (Rebro Rebro : Uzel.getRebros()) {
            LCSUzelStatus UzelStatus = statuses.get(Rebro.getEndUzel());
            if ((UzelStatus != null) && UzelStatus.isAllStrings()) {
                updFoundBeginIndes(beginIndes, endIndes, Rebro.getEndUzel(),
                            Dlina + getRebroDlina(Rebro), statuses, foundBeginIndes);
            } else {
                int stringNumber = getRebroStringNumber(Rebro);
                int beginInd = Rebro.getBeginInd() - Dlina;

                if ((beginInd < endIndes[stringNumber]) &&
                        (beginInd >= beginIndes[stringNumber]) &&
                        (foundBeginIndes[stringNumber] > beginInd)) {

                    foundBeginIndes[stringNumber] = beginInd;
                }
            }
        }
    }

    private boolean verifyFoundBeginIndes(int[] beginIndes) {
        for(int i=0; i<tekst.length; i++)
            if (beginIndes[i] == Integer.MAX_VALUE)
                return false;
        return true;
    }

    public List<comSubstr> diff() {
        Map<Uzel, LCSUzelStatus> statuses = new HashMap<Uzel, LCSUzelStatus>();
        getLCSUzelStatus(ST.getRootUzel(), 0, statuses);

        List<comSubstr> list = diff(getDefBeginIndes(), getDefEndIndes(), statuses);
        statuses.clear();

        return list;
    }

    private List<comSubstr> diff(int beginIndes[], int endIndes[], Map<Uzel, LCSUzelStatus> statuses) {
        comSubstr comSubstr = getLcs(beginIndes, endIndes, statuses);
        if (comSubstr == null)
            return new LinkedList<comSubstr>();

        List<comSubstr> prev = diff(beginIndes, comSubstr.beginIndes, statuses);
        List<comSubstr> next = diff(incIndes(comSubstr.endIndes), endIndes, statuses);

        prev.add(comSubstr);
        if (next != null)
            prev.addAll(next);
        return prev;
    }

    private int getRebroStringNumber(Rebro Rebro) {
        for (int i = 0; i < tekst.length; i++) {
            if (Rebro.getEndInd() <= getGSubLength(i))
                return i;
        }
        return -1;
    }

    private int getRebroDlina(Rebro Rebro) {
        return Rebro.getEndInd() - Rebro.getBeginInd();
    }

    private int getRebroDlinaForUzelStatus(Rebro Rebro) {
        int result = getRebroDlina(Rebro);

        int stringNumber = getRebroStringNumber(Rebro);
        if (Rebro.getEndInd() != getGSubLength(stringNumber))
            result += 1;
        return result;
    }

    private LCSUzelStatus getLCSUzelStatus(Uzel Uzel, int Dlina, Map<Uzel, LCSUzelStatus> statuses) {
        LCSUzelStatus UzelStatus = new LCSUzelStatus(Uzel, Dlina);
        if (Uzel.getRebros().size() == 0) {
            return UzelStatus;
        }

        for (Rebro Rebro : Uzel.getRebros()) {
            LCSUzelStatus status = getLCSUzelStatus(Rebro.getEndUzel(),
                    Dlina + getRebroDlinaForUzelStatus(Rebro), statuses);

            status.addString(getRebroStringNumber(Rebro));
            UzelStatus.mergeStatus(status);
        }
        statuses.put(Uzel, UzelStatus);
        return UzelStatus;
    }

    public String getGString() {
        return G;
    }

     private class LCSUzelStatus {
        private Uzel Uzel;
        private boolean allStrings;
        private Set<Integer> stringSet;
        private int Dlina;

        public LCSUzelStatus(Uzel Uzel, int Dlina) {
            this.Uzel = Uzel;
            allStrings = false;
            stringSet = new HashSet<Integer>();

            this.Dlina = Dlina;
        }

        public boolean isAllStrings() {
            if (!allStrings) {
                for (int i = 0; i < tekst.length; i++) {
                    if (!stringSet.contains(i))
                        return false;
                }
                allStrings = true;
            }
            return allStrings;
        }

        public void addString(int number) {
            if (!isAllStrings()) {
                if (!stringSet.contains(number))
                    stringSet.add(number);
            }
        }

        public int getDlina() {
            return Dlina;
        }

        public Uzel getUzel() {
            return Uzel;
        }

        public void mergeStatus(LCSUzelStatus status) {
            allStrings |= status.allStrings;
            if (!isAllStrings()) {
                stringSet.addAll(status.stringSet);
            }
        }
    }



}
